package _2022.hot100._416_分割等和子集;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author： YHSimon
 * @date： 2022-06-05 09:17
 */
public class Solution {
    // 24 ms
    public boolean canPartition3(int[] nums){
        int n=nums.length;
        if(n<2){
            return false;
        }
        int sum=0,maxNum=0;
        for(int num:nums){
            sum+=num;
            maxNum=Math.max(maxNum, num);
        }
        if(sum%2!=0) return false;
        int target=sum/2;
        if(maxNum>target){
            return false;
        }
        boolean[][] dp=new boolean[n][target+1];
        for(int i=0;i<n;i++){
            dp[i][0]=true;
        }
        dp[0][nums[0]]=true;
        for(int i=1;i<n;i++){
            int num=nums[i];
            for(int j=1;j<=target;j++){
                if(j>=num){
                    dp[i][j]=dp[i-1][j]|dp[i-1][j-num];
                }else{
                    dp[i][j]=dp[i-1][j];
                }
            }
        }
        return dp[n-1][target];
    }

    // 回溯 超时
    public boolean canPartition2(int[] nums){
        List<List<Integer>> combinations=new ArrayList<>();
        List<Integer> combine=new ArrayList<>();
        int sum=0;
        for(int i:nums){
            sum+=i;
        }
        if(sum%2==1) return false;
        dfs(nums,combinations,combine,0,sum/2);
        System.out.println(combinations);
        return combinations.size()>0;
    }

    private void dfs(int[] nums, List<List<Integer>> combinations, List<Integer> combine, int start,int sum) {
        if(sum<0){return;}
        if(sum==0){
            combinations.add(new ArrayList<>(combine));
        }
        for(int i=start;i<nums.length;i++){
            combine.add(i);
            dfs(nums, combinations, combine, i+1, sum-nums[i]);
            combine.remove(combine.size()-1);
        }
    }



    // 错误
    public boolean canPartition(int[] nums){
        int n=nums.length;
        if(n==1) return false;
        Arrays.sort(nums);
        int left=0,right=0;

        for(int i=0;i<n;i++){
            left+=nums[i];
        }
        for(int j=n-1;j>0;j--){
            right+=nums[j];
            left-=nums[j];
            if(left==right){
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        // System.out.println(s.canPartition2(new int[]{1,5,11,5}));
        // System.out.println(s.canPartition2(new int[]{1,2,3,5}));
        System.out.println(s.canPartition2(new int[]{2,2,1,1}));
    }
}
